package 极客算法训练营.chapter04;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * push(x) —— 将元素 x 推入栈中。
 * pop() —— 删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 *
 */
public class MinStack {
    private int size = 16;
    /** initialize your data structure here. */
    private int[] array = new int[size];
    private int topIndex = 0;
    private int min = Integer.MAX_VALUE;

    //数组自动扩容
    private void checkSize() {
        if (topIndex > size * 3 / 4){
            size *= 2;
            int[] copy = new int[size];
            System.arraycopy(array, 0, copy, 0, topIndex);
            array = copy;
        }
    }

    public MinStack() {
    }

    public void push(int x) {
        checkSize();
        array[topIndex++] = x;
        this.min = x < min ? x : min;
    }

    public void pop() {
        if (topIndex == 0) return;
        if (top() == min) {
            this.min = Integer.MAX_VALUE;
            for (int i = 0; i < topIndex - 1 ; i++) {
                this.min = array[i] < min ? array[i] : min;
            }
        }
        array[topIndex--] = 0;
    }

    public int top() {
        if (topIndex == 0) {
            return 0;
        }
        return array[topIndex - 1];
    }

    public int getMin() {
        return this.min;
    }

    class MinStacka {
        // 存储整个stack中的最小值
        private int min = Integer.MAX_VALUE;
        private int[] arrs = new int[10];
        private int index = 0;

        /**
         * initialize your data structure here.
         */
        public MinStacka() {

        }

        public void checkGrowth() {
            if (index >= arrs.length - 1) {
                // 使用右移位运算符，每次扩容一半
                this.arrs = Arrays.copyOf(this.arrs, this.arrs.length + (this.arrs.length >> 1));
            }
        }

        public boolean isEmpty() {
            return this.index <= 0;
        }

        public void push(int x) {
            // 判断是否扩容
            checkGrowth();
            int min = this.min;
            if ( min > x) {
                this.min = x;
            }
            // 加入
            arrs[index] = x;
            index++;
        }

        public int pop() {
            // pop的时候先将下标指针-1, 然后找出此时栈中的最小值,赋值给this.min
            int top = top();
            this.index--;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < this.index; i++) {
                if (min > this.arrs[i]) {
                    min = this.arrs[i];
                }
            }
            this.min = min;
            return top;
        }

        public int top() {
            if (this.isEmpty()) {
                throw new EmptyStackException();
            }
            // 指针前移一位
            return this.arrs[this.index - 1];
        }

        public int getMin() {
            return this.min;
        }
    }
}
